package com.linyaonan.leetcode.medium._230;

import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.TreeSet;

/**
 * 给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。
 * <p>
 * 说明：
 * 你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。
 * <p>
 * 示例 1:
 * <p>
 * 输入: root = [3,1,4,null,2], k = 1
 * 3
 * / \
 * 1   4
 * \
 *    2
 * 输出: 1
 * 示例 2:
 * <p>
 * 输入: root = [5,3,6,2,4,null,null,1], k = 3
 * 5
 * / \
 * 3   6
 * / \
 * 2   4
 * /
 * 1
 * 输出: 3
 * 进阶：
 * 如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化 kthSmallest 函数？
 *
 * @author: Lin
 * @date: 2020/1/18
 */
public class KthSmallestElement {

    int t = 0;
    int result = 0;
    public int kthSmallest(TreeNode root, int k) {
        // 目标值
        t = k;
        try {
            dfs(root);
        } catch (Exception e) {
            return result;
        }
        return result;
    }

    private void dfs(TreeNode node) {
        if(node != null) {
            dfs(node.left);
            if (--t == 0) {
                result = node.val;
                throw new RuntimeException("get it");
            }
            dfs(node.right);
        }
    }
}
